One of the most common challenges facing hardware system designers is the coordination of event scheduling for a large number N of processes. Each one of the N processes has a “next event time” when that process needs to be handled. In the art, “handling” includes, but is not limited to: short duration event specific processing as well as the initiation of long duration data processing. An event scheduler is used to initiate handling for respective processes at appropriate corresponding times.
For hardware event scheduling implementations, it is common to identify processes requiring handling at appropriate corresponding times by repetitive scanning through information. Upon each tick of a clock signal information associated with all processes is scanned to identify events to be handled. Such traditional methods may be satisfactory for application scheduling a relatively small number of processes making use of a given handling speed (low density applications). However, as the number N of processes to be scheduled increases while the handling speed is kept the same (high density applications), such solutions become less and less viable. A frequently observed impediment with the scanning approach is the tight time budget available to scan through the information. As the number of processes N becomes large or as the time budget becomes small, such solutions prove to be unscalable.
To alleviate the scalability issue, hardware system architects typically opt to divide the N processes into m groups of size N/m, and devote a scanning scheduler to each N/m group of processes. Although providing a measure of relief, as the number of processes N increases so must m increase to compensate. This means that m scanning scheduler implementations must be used to scan in parallel which represents a large expenditure of hardware logic. Either the hardware costs of parallelism become too high, or the time budget for handling each process becomes too small therefore leading to unscalable solutions.
Although the hardware scheduling of multiple processes spans a wide variety of applications, the invention will be presented herein with respect to convergent technologies and products, and in particular with respect to telephony applications addressing a current need in the market. Convergent technologies concern the merging of voice, data, and video provisioning over the same data transport network by integrating telecommunications and computer technologies.
In support of telephony applications, an exemplary data streaming service, the Voice-over-Internet Protocol (VoIP) service may be employed. VoIP technologies are used for provisioning telephone-quality sessions over packet-switched data transport networks. Exemplary data-stream processing equipment provisioning VoIP services includes: switching nodes, routers, multiplexers, demultiplexers, mixers, etc. of particular mention are VoIP telephony convergent products which require the handling of a large number of voice data streams, where the handling includes at least the initiation of timed audio playback of voice data samples.
From a hardware implementation perspective, each voice data stream is referred to as a process which needs to be handled by timely processing data associated therewith. Timely playback of the data requires scheduling. Hardware solutions to efficient playback scheduling are sought for provisioning a large number of telephone sessions in an efficient and scalable manner at higher and higher stream densities driven by an increased demand for provisioned services. Factors to be considered include: timing information embedded in the conveyed data stream and therefore not available for a priori scheduling, and a likely possibility that the voice data conveyed in packets associated with each data stream is not conveyed sequentially.
A simple exemplary prior art method of multi-process scheduling is presented in FIG. 1. Incoming VoIP packets 100 are received 102 via an associated packet-switched data transport network (not shown). The packets 100, conveying VoIP data, are typically buffered in a packet buffer 110.
Each packet has a header and a payload. The VoIP packet payload carries voice sample data. Information conveyed in the VoIP packet header is used to derive a voice stream identification (streamID) to associate the payload of the VoIP packet with a particular voice data stream. Each VoIP packet header further specifies a data-stream segment time-index value to sequence the payload with respect to the particular voice data stream. The header may implicitly specify the streamID. The streamID may be determined by classifying the packet based on packet header fields such as the Internet Protocol (IP) address, User Datagram Protocol (UDP) port number, etc.
Ultimately the voice sample data conveyed by the VoIP packets is played back to a human. In accordance with the exemplary data streaming service presented, voice samples are generated and have to be played back at 125 μs intervals. The human auditory system provides some degree of flexibility in interpreting played back audio signals.
Therefore in accordance with a prior art multi-process scheduling implementation presented, a scheduler 120 is responsive to a 8 kHz clock signal 122 from a system clock 124. The 8 kHz clock signal divides the operation of the scheduler 120 into 125 μs intervals. During each 125 μs interval, the scheduler 120 performs a search 130. The search 130 scans 132 the contents of the packet buffer 110 and identifies 134, based on VoIP packet header time index values, which voice sample data 136 needs to be provided 138 to a playback module 140 for playback. As multiple streams are to be handled simultaneously in support of multiple simultaneous telephone sessions, it is expected that multiple processes may be required to start playback during the same 125 μs interval. A handling sequence generated by three consecutive scans 132 is presented schematically in FIG. 1 where: one packet (1) is identified for handling in the first scan, two packets (2) are identified for handling in the second scan, and one packet (3) is identified for handling in the third scan.
The playback module 140 is provided 138 with the identified packets 136 requiring handling. The playback module 140 makes use of the streamID information associated with the identified packets to associate with, and play back the voice samples in connection with, respective audio streams for respective telephone sessions. The contents of the identified packets begin playback subsequent to having been identified and continue playback during subsequent 125 μs time intervals simultaneously with other voice sample data until all voice data samples conveyed by respective packets have been played back. The operation of the playback module 140 is beyond the scope of the present description and described elsewhere. The playback module 140 is responsible for freeing up storage space held by packets after having been played back.
In accordance with the simple search 130 presented with respect to the exemplary prior art implementation, the scheduler 120 inspects the entire contents of the packet buffer 110. All of the packets 100 are inspected during each scan 132 regardless of whether they require handling or not. The packet buffer 110 may contain more than one VoIP data packet per VoIP data stream (telephone session).
It is very likely in employing packet-switched data transport that packets arrive out of sequence. The large overhead incurred by the repetitive scanning 132 does provide a benefit of identifying packets to be handled in the correct sequence without actively sorting the received packets. Repetitive scanning 132 takes care of sequencing packets received out of sequence.
The above search 130 example is rather simplistic but is intended to present the relevant principles. It is understood in the art that the information sought by the scan 132 is found solely in packet headers. Therefore only packet headers are scanned 132 to identify the next packets to be played back. It is understood that the packet header scanning 132 incurs an overhead in keeping track of memory storage locations where the packet headers are to be found. Keeping track of packet header storage locations is typically implemented via a table lookup.
The time taken to perform such a search 130 therefore increases with the total number of VoIP packets stored in the buffer and therein lies a scalability problem. In using the term “scalability problem” it is understood that: using the scheduler 120 to scan 132 the entire contents of the packet buffer, will be less and less of a viable solution with increased throughput of data, in support of more simultaneous telephone sessions.
An observed problem is that many packet headers are inspected unnecessarily as more than one data packet having the same streamID is typically stored in the packet buffer 110. Therefore as packet throughput is increased, in support of a greater number of simultaneous telephone sessions, it becomes more and more difficult to scan packet headers during the 125 μs interval.
In order to be able to handle more data packets in support of more data streams (telephone sessions), it is necessary to utilize multiple m arrangements shown in FIG. 1 in parallel. The parallel scheduling of data streams would further suffer from an incurred processing overhead in distributing the incoming packets 102 over the m packet buffers 110.
Put another way, relevant indicia of the operation of such implementations is the number of packets K stored in the packet buffer 110. The overhead incurred in scanning 130 the packet buffer 110 varies proportionally with K. The overhead may be distributed using multiple arrangements m. The processing overhead required in implementing the above is said to be Order(K/m) where K/m represents the amount of data per packet buffer or the number of data packets per packet buffer respectively. It will be noted that in accordance with these implementations, the number of actually provisioned data stream processes (telephone sessions) N is not equal to K.
Therefore the scanning 132 of the entire packet buffer 110 is considered impractical for VoIP telephony applications but may be a viable hardware scheduling solution for other applications.
In accordance with yet another prior art improvement presented in FIG. 2, the incoming VoIP packets 102 are pre-processed by a queue manager 202. The queue manager 202 operates in conjunction with queues 210, each of which is associated with an individual VoIP data stream (telephone session). The queue manager 202, upon receipt of each VoIP packet, derives 204 the streamID specified in the packet header, adds 206 the VoIP packet to the corresponding queue 210, and sorts 208 the packets stored in the streamID queue 210 with respect to time index values thereof. The sorting of stream queues 210 is necessary and re-sequences packets 102 arriving out of sequence, as is typically the case.
Although the sorting of the queue 210 is presented herein for easy understanding of the relevant concepts, in practice, such a necessary step is considered to introduce large processing overheads. Typically the same result is achieved by inserting memory address references to the newly stored received packet into a list of references sorted according to corresponding packet time index values. The implementation of the list of references requires additional resources. The implementation further suffers from independent multi-queue storage reservations which were otherwise consolidated in the implementation presented above.
The arrangement presented in FIG. 2, enables a scheduler 220 to inspect only one packet per VoIP stream in identifying data streams requiring handling during a 125 μs interval. The pre-processing performed by the queue manager 202 enables the scheduler 220 to scan only the heads-of-line of the time-index sorted streamID queues 210.
Even with the improvement presented above, the 125 μs time budget still provides a limit as to how many streamID queues 210 can be scanned 232. For example, as the scheduler 202 scans 232 all N stream queues 210: only two streams (1) are found to require handling during a first 125 μs interval, and one stream (2) is found to require handing during a second 125 μs interval. A large overhead is therefore incurred in inspecting stream queues 210 which do not require handling during a particular 125 μs interval. This implementation is regarded as non-scalable for this very reason as well. Additional data stream handling capacity may be provided by using multiple m arrangements such as shown in FIG. 2.
Put another way, relevant indicia of the operation of such an implementation is the number N of stream queues 210. The overhead incurred in scanning 232 varies proportionally with N. The overhead may be distributed using multiple arrangements m. The processing overhead required in implementing the above is said to be Order(N/m) where N/m is the number of stream queues 210 per arrangement.
The above presented prior art implementations suffer from the need of redevelopment as additional VoIP data stream handling capacity is needed thereby further contributing to the scalability problem.
There therefore is a need to solve the above mentioned non-scalability issues.